package arithmetic.leetCode;

import arithmetic.geektime.tree.TreeNode;
import arithmetic.geektime.tree.TreeTraverse;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 此层序遍历方式未使用 Queue
 *
 * @author dycong
 * @date 2019/11/21 10:37
 */
public class TreeLevelTraversal_102_Fast {


    public static void main(String[] args) {
        TreeTraverse.TreeHelper treeHelper = new TreeTraverse.TreeHelper();
        TreeNode root = treeHelper.getTree(5);
        TreeLevelTraversal_102_Fast twoSum_1 = new TreeLevelTraversal_102_Fast();
        long t = System.currentTimeMillis();
        System.out.println(twoSum_1.levelOrder(root));
        System.out.println("耗时: " + (System.currentTimeMillis() - t) + "ms");
        t = System.currentTimeMillis();
        System.out.println(twoSum_1.levelOrder_(root));
        System.out.println("耗时: " + (System.currentTimeMillis() - t) + "ms");
        t = System.currentTimeMillis();
        System.out.println(twoSum_1.levelOrder_2(root));
        System.out.println("耗时: " + (System.currentTimeMillis() - t) + "ms");
    }

    /**
     * 无递归，稍快
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<List<Integer>> ans = new ArrayList<>();
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);

        while (!nodes.isEmpty()) {
            nodes = levelOrder(nodes, ans);
        }
        return ans;
    }

    public List<TreeNode> levelOrder(List<TreeNode> nodes, List<List<Integer>> ans) {
        if (nodes.isEmpty()) return Collections.emptyList();

        List<TreeNode> nextLevelNodes = new ArrayList<>();
        List<Integer> levelValues = new ArrayList<>();
        for (TreeNode node : nodes) {
            levelValues.add(node.val);
            if (node.left != null) {
                nextLevelNodes.add(node.left);
            }
            if (node.right != null) {
                nextLevelNodes.add(node.right);
            }
        }
        if (!levelValues.isEmpty()) {
            ans.add(levelValues);
        }
        return nextLevelNodes;
    }

    /**
     * 递归版 快
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder_2(TreeNode root) {
        if (root == null) return Collections.emptyList();
        List<List<Integer>> ans = new ArrayList<>();
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        levelOrder_2(nodes, ans);
        return ans;
    }

    public void levelOrder_2(List<TreeNode> nodes, List<List<Integer>> ans) {
        if (nodes.isEmpty()) return;

        List<TreeNode> nextLevelNodes = new ArrayList<>();
        List<Integer> levelValues = new ArrayList<>();
        for (TreeNode node : nodes) {
            levelValues.add(node.val);
            if (node.left != null) {
                nextLevelNodes.add(node.left);
            }
            if (node.right != null) {
                nextLevelNodes.add(node.right);
            }
        }
        if (!levelValues.isEmpty()) {
            ans.add(levelValues);
        }
        levelOrder_2(nextLevelNodes, ans);
    }


    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> levelOrder_(TreeNode root) {
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        levelOrder(nodes);
        return ans;
    }

    public void levelOrder(List<TreeNode> nodes) {
        if (nodes == null || nodes.size() < 1) {
            return;
        }
        List<TreeNode> nextLevelNodes = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for (TreeNode node : nodes) {
            if (node != null) {
                list.add(node.val);
                nextLevelNodes.add(node.left);
                nextLevelNodes.add(node.right);
            }
        }
        if (list.size() > 0) {
            ans.add(list);
            levelOrder(nextLevelNodes);
        }

    }

}
